package cn.zifangsky.hashtable.lfu;

import cn.zifangsky.hashtable.Map;
import cn.zifangsky.hashtable.SeparateChainHashTable;
import cn.zifangsky.linkedlist.LinkedList;

import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.ScheduledThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.function.Consumer;

/**
 * 基于“最近最不经常使用算法（LFU，也就是'The Least Frequently Used'）”的缓存队列实现
 *
 * @author zifangsky
 * @date 2020/6/25
 * @since 1.0.0
 */
public class LFUCache<K, V> {
    /**
     * 默认的缓存大小
     */
    public static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 单个节点信息
     */
    public static class Node<K, V> {
        /**
         * key
         */
        final K key;
        /**
         * value
         */
        V value;

        /**
         * 访问次数
         */
        int times;

        /**
         * 过期时间戳
         */
        long expired;

        /**
         * 上一个节点
         */
        Node<K, V> previous;

        /**
         * 下一个节点
         */
        Node<K, V> next;

        public Node(K key, V value) {
            this(key, value, -1);
        }

        public Node(K key, V value, long expired) {
            //设置初始访问次数为1
            this(key, value, 1, expired);
        }

        public Node(K key, V value, int times, long expired) {
            this(key, value, times, expired, null, null);
        }

        public Node(K key, V value, int times, long expired, Node<K, V> previous, Node<K,V> next) {
            this.key = key;
            this.value = value;
            this.times = times;
            this.expired = expired;
            this.previous = previous;
            this.next = next;
        }

        @Override
        public final String toString() {
            return key + "=" + value;
        }

        @Override
        public final boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Node<?, ?> node = (Node<?, ?>) o;
            return this.equals(key, node.key) &&
                    this.equals(value, node.value);
        }

        /**
         * 取 key 和 value 的 hashCode 的异或
         */
        @Override
        public final int hashCode() {
            return this.hashCode(key) ^ this.hashCode(value);
        }

        public int hashCode(Object o) {
            return o != null ? o.hashCode() : 0;
        }

        public boolean equals(Object a, Object b) {
            return (a == b) || (a != null && a.equals(b));
        }
    }

    /**
     * 定义一个桶结构的链表，相同访问次数的键值对放在一个桶中
     */
    public static class LinkedBucketList<K, V> {
        /**
         * 头节点
         */
        Node<K, V> head;
        /**
         * 尾节点
         */
        Node<K, V> tail;

        /**
         * 上一个桶
         */
        LinkedBucketList<K, V> previous;

        /**
         * 下一个桶
         */
        LinkedBucketList<K, V> next;

        /**
         * 当前桶的访问次数
         */
        int times;

        public LinkedBucketList(Node<K, V> node) {
            this.head = node;
            this.tail = node;
            this.previous = null;
            this.next = null;
            this.times = node.times;
        }

        /**
         * 返回当前桶是否已经空了
         * @return boolean
         */
        public boolean isEmpty(){
            return this.head == null;
        }

        /**
         * 向当前桶新增节点（新节点都放在链表尾部）
         * @param newNode 新节点
         */
        public synchronized void add(Node<K, V> newNode){
            if(newNode == null){
                return;
            }

            if(this.tail == null){
                this.tail = newNode;
                this.head = this.tail;
            }else{
                this.tail.next = newNode;
                newNode.previous = this.tail;
                this.tail = newNode;
            }
        }

        /**
         * 移除头结点
         */
        public synchronized Node<K, V> removeHead(){
            if(this.head == null){
                return null;
            }

            Node<K, V> result = this.head;
            if(this.head == this.tail){
                this.head = null;
                this.tail = null;
            }else{
                this.head = this.head.next;
                this.head.previous = null;
                result.next = null;
            }

            return result;
        }

        /**
         * 移除尾结点
         */
        public synchronized Node<K, V> removeTail(){
            if(this.tail == null){
                return null;
            }

            Node<K, V> result = this.tail;
            if(this.head == this.tail){
                this.head = null;
                this.tail = null;
            }else{
                this.tail = this.tail.previous;
                this.tail.next = null;
                result.previous = null;
            }

            return result;
        }

        /**
         * 移除某个结点
         */
        public synchronized void remove(K key){
            if(key == null){
                return;
            }

            Node<K, V> temp = this.head;
            while (temp != null){
                if(key.equals(temp.key)){
                    this.remove(temp);
                    break;
                }
                temp = temp.next;
            }
        }

        /**
         * 移除过期节点
         */
        public synchronized LinkedList<Node<K, V>> removeExpiredNodes(){
            //所有已经过期的KEY
            LinkedList<Node<K, V>> expiredKeyList = new LinkedList<>();
            //当前精确到毫秒的时间戳
            long current = System.currentTimeMillis();

            Node<K, V> temp = this.head;
            while (temp != null){
                //如果当前节点已经过期，则移除，并继续检查下一个节点
                if(temp.expired > 0 && temp.expired <= current){
                    expiredKeyList.add(temp);
                    this.remove(temp);
                }
                temp = temp.next;
            }

            return expiredKeyList;
        }

        /**
         * 移除指定节点
         */
        public void remove(Node<K, V> temp){
            if(temp == this.head){
                this.removeHead();
            }else if(temp == this.tail){
                this.removeTail();
            }else{
                temp.previous.next = temp.next;
                temp.next.previous = temp.previous;
            }
        }
    }


    /* ---------------- Fields -------------- */

    /**
     * 检查失效键值对的定时任务
     */
    private ScheduledExecutorService checkScheduledExecutor;

    /**
     * 缓存容量
     */
    private final int capacity;

    /**
     * 目前缓存了多少个键值对
     */
    private int size;

    /**
     * 最左边的桶
     */
    private LinkedBucketList<K, V> headBucketList;

    /**
     * 定义一个Map，为了方便取数据
     */
    private Map<K, Node<K, V>> keyNodeMap;

    /**
     * 定义一个Map，为了方便得到KEY所在的桶
     */
    private Map<K, LinkedBucketList<K, V>> keyBucketMap;


    public LFUCache() {
        this(DEFAULT_INITIAL_CAPACITY, true);
    }

    /**
     * @param capacity CACHE容量
     */
    public LFUCache(int capacity) {
        this(capacity, true);
    }

    /**
     * @param capacity CACHE容量
     * @param autoCheckExpiredKey 是否自动检查失效的键值对
     */
    public LFUCache(int capacity, boolean autoCheckExpiredKey) {
        this.capacity = capacity;
        this.headBucketList = null;
        this.keyNodeMap = new SeparateChainHashTable<>();
        this.keyBucketMap = new SeparateChainHashTable<>();

        if(autoCheckExpiredKey){
            this.initCheckScheduledExecutor();
        }
    }

    /**
     * 缓存的键值对数量
     */
    public int size(){
        return this.size;
    }

    /**
     * 通过KEY取值
     * @param key KEY
     * @return V
     */
    public synchronized V get(K key){
        if(key == null){
            return null;
        }

        //1. 获取数据节点
        Node<K, V> data = this.keyNodeMap.get(key);
        if(data == null){
            return null;
        }

        long expired = data.expired;
        long current = System.currentTimeMillis();

        //2. 判断该节点是否已经过期，如果已经过期，则需要删除
        if(expired > 0 && expired <= current){
            this.remove(data, false);
            return null;
        }
        //3. 否则将该节点的访问次数+1，并移动到新的桶
        else{
            data.times = data.times + 1;

            LinkedBucketList<K, V> bucketList = this.keyBucketMap.get(key);
            this.move(data, bucketList);
        }

        //4. 返回结果
        return data.value;
    }

    /**
     * PUT操作，并设置为永不过期
     * @param key KEY
     * @param value VALUE
     */
    public synchronized void put(K key, V value){
        this.put(key, value, -1);
    }

    /**
     * PUT操作，并设置过期时间
     * @param key KEY
     * @param value VALUE
     * @param seconds X秒后过期
     */
    public synchronized void put(K key, V value, int seconds){
        this.put(key, value, seconds, TimeUnit.SECONDS);
    }

    /**
     * PUT操作，并设置过期时间
     * @param key KEY
     * @param value VALUE
     * @param time 过期时间
     * @param unit 过期单位
     */
    public synchronized void put(K key, V value, int time, TimeUnit unit){
        if(key == null || unit == null){
            throw new IllegalArgumentException("参数存在异常！");
        }

        //1. 计算过期时间戳，并创建新节点
        Node<K, V> newNode;
        if(time > 0){
            long expired = System.currentTimeMillis() + unit.toMillis(time);
            newNode = new Node<>(key, value, expired);
        }else{
            newNode = new Node<>(key, value);
        }

        //2. 查询节点是否存在，如果存在则：
        Node<K, V> savedNode = this.keyNodeMap.get(key);
        if(savedNode != null){
            newNode.times = savedNode.times + 1;

            //2.1 获取该节点所在的桶
            LinkedBucketList<K, V> bucketList = this.keyBucketMap.get(key);

            //2.2 移动该节点到后面的桶
            this.move(newNode, bucketList);
        }
        //3. 如果不存在，则当做新节点插入
        else{
            //3.1 首先检查当前缓存的剩余容量是否足够，如果容量不足，则删除过期和访问次数最少的数据
            if(this.size >= capacity){
                //3.1.1 删除过期数据
                this.removeExpiredData();

                //3.1.2 如果容量还不足，则从最左边的桶的头结点开始删除访问次数最少的数据
                while (this.size >= capacity){
                    Node<K, V> headNode = this.headBucketList.head;
                    this.remove(headNode, false);
                }
            }

            //3.2 如果最左边的桶为null（也就是说当前一个节点都没有），则直接给最左边的桶赋值即可
            if(this.headBucketList == null){
                this.headBucketList = new LinkedBucketList<>(newNode);
            }
            //3.3 如果最左边的桶存在（也就是说当前已经缓存了一些键值对）
            else{
                //如果当前最左边的桶恰好装了访问次数为1的节点
                if(this.headBucketList.times == newNode.times){
                    this.headBucketList.add(newNode);
                }else{
                    //否则需要重新设置最左边的桶
                    LinkedBucketList<K, V> newHeadBucketList = new LinkedBucketList<>(newNode);

                    newHeadBucketList.next = this.headBucketList;
                    this.headBucketList.previous = newHeadBucketList;
                    this.headBucketList = newHeadBucketList;
                }
            }

            this.keyBucketMap.put(key, headBucketList);
            this.size++;
        }
        this.keyNodeMap.put(key, newNode);
    }

    /**
     * 移除指定的KEY
     * @param key KEY
     */
    public synchronized void remove(K key){
        if(key == null){
            throw new IllegalArgumentException("参数存在异常！");
        }

        Node<K, V> node = this.keyNodeMap.get(key);
        if(node != null){
            this.remove(node, false);
        }
    }

    /**
     * 遍历所有键值对
     * @param action action
     */
    public void forEach(Consumer<? super Node<K, V>> action){
        this.keyNodeMap.forEach((k, node) -> {
            action.accept(new Node<>(node.key, node.value, node.times, node.expired));
        });
    }

    /**
     * 删除指定节点
     * @param node 指定节点
     * @param deleted 用于标识是否已经在 LinkedBucketList 删除
     */
    private void remove(Node<K, V> node, boolean deleted){
        //1. 判断待删除节点是否存在
        if(node == null){
            return;
        }

        //2. 如果存在，则依次删除
        LinkedBucketList<K, V> bucketList = this.keyBucketMap.get(node.key);
        this.size--;
        if(!deleted){
            bucketList.remove(node);
        }

        this.keyNodeMap.remove(node.key);
        this.keyBucketMap.remove(node.key);

        //3. 如果必要，则重新平衡最左边的桶
        this.reBalanceHeadBucketList(bucketList);
    }

    /**
     * 当某个节点被多次访问时，将其移动到“访问次数+1”的桶中
     * @param oldNode 待移动节点
     * @param oldBucketList 待移动节点所在的桶
     */
    private void move(Node<K, V> oldNode, LinkedBucketList<K, V> oldBucketList){
        //1. 先删除旧桶中的节点并清除旧节点的关联关系
        oldBucketList.remove(oldNode);
        oldNode.previous = null;
        oldNode.next = null;

        //2. 如果必要，则重新平衡最左边的桶
        boolean reBalance = this.reBalanceHeadBucketList(oldBucketList);

        //3. 将其移动到“访问次数+1”的桶中
        LinkedBucketList<K, V> previousBucketList = reBalance ? oldBucketList.previous : oldBucketList;
        LinkedBucketList<K, V> nextBucketList = oldBucketList.next;

        //3.1 如果当前节点后面这个桶为null
        if(nextBucketList == null){
            //则创建新的桶
            LinkedBucketList<K, V> newBucketList = new LinkedBucketList<>(oldNode);

            newBucketList.previous = previousBucketList;
            if(previousBucketList != null){
                previousBucketList.next = newBucketList;
            }
            if(this.headBucketList == null){
                this.headBucketList = newBucketList;
            }

            this.keyBucketMap.put(oldNode.key, newBucketList);
        }
        //3.2 如果当前节点后面这个桶已经存在
        else {
            //如果当前节点后面这个桶恰好为“访问次数+1”的桶
            if(nextBucketList.times == oldNode.times){
                nextBucketList.add(oldNode);
                this.keyBucketMap.put(oldNode.key, nextBucketList);
            }else{
                //否则需要创建新的桶
                LinkedBucketList<K, V> newBucketList = new LinkedBucketList<>(oldNode);

                if(previousBucketList != null){
                    previousBucketList.next = newBucketList;
                }
                newBucketList.previous = previousBucketList;
                newBucketList.next = nextBucketList;
                nextBucketList.previous = newBucketList;

                if(this.headBucketList == nextBucketList){
                    this.headBucketList = newBucketList;
                }

                this.keyBucketMap.put(oldNode.key, newBucketList);
            }
        }
    }

    /**
     * 删除一个节点后，重新平衡最左边的桶
     * @param bucketList 删除节点的桶
     * @return 返回是否重平衡了
     */
    private boolean reBalanceHeadBucketList(LinkedBucketList<K, V> bucketList){
        //1. 如果当前桶还有剩余节点，则不做处理
        if(!bucketList.isEmpty()){
            return false;
        }

        //2. 如果当前桶已经是最左边的桶，则需要将其右边那个桶作为新的“最左边的桶”
        if(bucketList == this.headBucketList){
            this.headBucketList = bucketList.next;

            if(this.headBucketList != null){
                this.headBucketList.previous = null;
            }
        }
        //3. 如果当前桶在中间，则将其左右的桶关联起来
        else {
            bucketList.previous.next = bucketList.next;
            if(bucketList.next != null){
                bucketList.next.previous = bucketList.previous;
            }
        }

        return true;
    }

    /**
     * 移除过期数据
     */
    private synchronized void removeExpiredData(){
        LinkedBucketList<K, V> bucketList = this.headBucketList;

        while (bucketList != null){
            //1. 获取过期的key
            LinkedList<Node<K, V>> expiredKeyList = bucketList.removeExpiredNodes();
            //2. 依次移除并重新平衡最左边的桶
            expiredKeyList.forEach(node -> this.remove(node, true));
            //3. 检查下一个桶是否存在过期的key
            bucketList = bucketList.next;
        }
    }

    /**
     * 初始化定时任务
     */
    private void initCheckScheduledExecutor(){
        if(this.checkScheduledExecutor != null){
            return;
        }

        //1. 定义一个1个线程的定时任务
        this.checkScheduledExecutor = new ScheduledThreadPoolExecutor(1, r -> {
            Thread thread = new Thread(r);
            thread.setDaemon(true);
            thread.setName("check-thread-fifo");

            return thread;
        });

        //2. 设置执行频率（2秒钟校验一次）
        this.checkScheduledExecutor.scheduleWithFixedDelay(this::removeExpiredData, 2, 2, TimeUnit.SECONDS);
    }

}
